#!/usr/bin/env python

# (c) Copyright 2008 Paul Hankin. All Rights Reserved. 

import itertools
import re
import operator
import copy
import graphics
import binascii
import importers

def all_rolls():
    "Generate all rolls, larger die first"
    for d0 in xrange(1, 7):
        for d1 in xrange(1, d0 + 1):
            yield (d0, d1)

# Inherit from tuple because it makes our class a lot faster.
class Board(tuple):
    @property
    def pipcounts(board):
        "Return pipcounts for both players"
        p0, p1 = 0, 0
        for i in xrange(1, 26):
            p0 += i * board[i] * (board[i] > 0)
            p1 -= i * board[-i - 1] * (board[-i - 1] < 0)
        return p0, p1
        
    @property
    def positionID(self):
        "Generate a 14 character ID uniquely describing a board."
        # This encoding only works for up to 30 men in play.
        assert sum(abs(k) for k in self) <= 30
        def bits():
            """Generate 80 bits describing the board. 0 means next
               point, and 1 means add a man to the current point. Player 0's
               men are described first, followed by player 1's.
               80 = (number of players) * (number of points + number of men)
                  = 2 * (25 + 15)
               If a player has less than 15 men on the board the total number
               of bits will be less than 80. The stream is padded with 0's
               at the end to cope with this.
            """
            for player in xrange(2):
                for i in xrange(1, 26):
                    pt = 25 - i if player else i
                    sign = -1 if player else 1
                    for j in xrange(max(self[pt] * sign, 0)):
                        yield 1
                    yield 0
            for pad in xrange(sum(self.men_off)):
                yield 0
        # Generate the stream of bits.
        b = bits()
        # Encode the bits into 10 8-bit bytes.
        code = [chr(sum(b.next() << i for i in xrange(8))) for j in xrange(10)]
        # And base-64 encode them.
        # b2a_base64 pads to a multiple of 4 characters, and appends \n.
        # We want 14 characters (14 * 6 = 84 [6 = bit per character in base
        # 64]) so we need to throw 3 characters away from the end.
        return binascii.b2a_base64(''.join(code))[:-3]
        
    @staticmethod
    def from_positionID(position_id):
        "Create a board from a position ID."
        assert len(position_id) == 14
        # a2b_base64 required 4-byte padding.
        code = binascii.a2b_base64(position_id + '==')
        def bits(bytes):
            for b in map(ord, bytes):
                for i in xrange(8):
                    yield (b >> i) & 1
        i, points = 0, [0] * 26
        for b in bits(code):
            player, pt = i // 25, i % 25
            if b:
                # Bit found: add a man to the current point.
                points[24 - pt if player else pt + 1] += (1, -1)[player]
            else:
                # No bit found: go to the next point.
                i += 1
        return Board(points)
            
    @classmethod
    def from_points(cls, *args):
        "Given points and number of men, return a board structure."
        points = [0] * 26
        for (p, n) in args:
            if p < 0:
                p = 25 + p
            assert p in xrange(0, 26)
            assert points[p] == 0
            points[p] = n
        return cls(points)
    @property
    def men_off(self):
        return [max(0, 15 - sum(j * i for i in self if i * j > 0))
            for j in (1, -1)]
    def reverse(self):
        """Swap the board round, producing board from other player's
        perspective"""
        return Board(-i for i in reversed(self))

    def __str__(self):
        return graphics.toString_ascii(self, False)
                
initialPosition = Board.from_points(
    (24, 2), (13, 5), (8, 3), (6, 5), (-24, -2), (-13, -5), (-8, -3), (-6, -5))

class MoveException(Exception):
    pass

class Move(object):
    """An object representing a move. Constructed from a board and a
    list of basic movements, it's converted lazily to a user-readable string
    in normal backgammon notation."""
    def __init__(self, board, *from_to):
        assert all(len(m) == 2 for m in from_to)
        self._board = board
        self._from_to = from_to
    move_mult = re.compile(r'^(.*?)(\((\d)\))?$')
    move_valid = re.compile(r'((\d+|bar)(/(\d+|off|bar)\*?)+(\(\d\))? *)+')
    
    def __nonzero__(self):
        return len(self._from_to) > 0
        
    def __iter__(self):
        for m in self._from_to:
            yield m
    
    @property
    def board(self): return self._board
    @property
    def board_after(self):
        "Return the game board after the move is played."
        if getattr(self, '_board_after', None): # Cache
            return self._board_after
        # Create a mutable version of the board for we are going to modify it
        board = list(self._board)
        for move in self._from_to:
            if board[move[0]] <= 0: raise MoveException()
            # Remove any blots we may have hit
            for w in (m for m in move if board[m] == -1 and m > 0):
                board[w], board[0] = 0, board[0] - 1
            if not all(board[w] >= 0 for w in move if w > 0):
                raise MoveException()
            # Apply the move (careful - point 0 is off rather than opps bar)
            board[move[0]] -= 1
            if move[-1] > 0:
                board[move[-1]] += 1
        self._board_after = Board(board)
        return self._board_after
    
    @classmethod
    def from_string(cls, board, move):
        """Parse moves of the form 'a[/b\\*?]*/c\\*?(\(n\))'
        where a, b, c are 1..24 or bar or off. Each move is separated
        by spaces. Returns a Move object."""
        assert cls.move_valid.match(move), "%s is not valid" % move
        moves = move.split()
        fts = []
        for m in moves:
            # Remove *'s as they aren't necessary
            m = m.replace('*', '')
            # Separate move from multiplicity
            m = cls.move_mult.match(m)
            m, mult = m.group(1), m.group(3)
            mult = int(mult) if mult else 1
            steps = m.split('/')
            steps = map(cls._point_from_name, steps)
            for i in xrange(len(steps) - 1):
                fts.extend([(steps[i], steps[i + 1])] * mult)
        # Make sure our moves are highest-checker first.
        fts.sort(cls.move_order)
        return cls(tuple(board), *fts)
    @staticmethod
    def move_order(a, b):
        # Highest checker comes first
        if a[0] < b[0]: return 1
        if a[0] > b[0]: return -1
        # Furthest move comes first
        if a[-1] < b[-1]: return -1
        if a[-1] > b[-1]: return 1
        # Most hits comes first (or break ties using default comparison)
        return (len(b) - len(a)) or cmp(a, b)
    def str_simple(self):
        """A simple representation of the move. Each checker move is written
        out in full"""
        return ' '.join('%d/%d' % (f, t) for f, t in self._from_to)
    def __str__(self):
        if not hasattr(self, '_move'):
            self._move = self._make_move(self._board, list(self._from_to))
        return self._move
    @staticmethod
    def _point_name(x, d={0:'off', 25:'bar'}):
        "Map point numbers to names. 0 is off, 25 is the bar."
        return d.get(x, x)
    @staticmethod
    def _point_from_name(n, d={'off':0, 'bar':25}):
        "Map a string representing a point to its point number."
        return int(d.get(n, n))
    @staticmethod
    def _join_combo(moves):
        """Find and remove a combination move and return True, or
         return False if no combination exists."""
        for i in xrange(len(moves) - 1):
            for j in xrange(i + 1, len(moves)):
                if moves[i][-1] == moves[j][0]:
                    moves[i] = moves[i][:-1] + moves[j]
                    del moves[j]
                    return True
        return False
    def _nice_move(self, move, mult, hit_set, board):
        """Nicely format a single move, returning a string of the form
           eg: 24/18*/12 or 13/8 or 13/9* or 13/7(2).
        move is a list of moves a single checker makes.
        mult is the number of checkers that share this move
        hit_set is a set of points on which a hit has already been noted.
        board is the starting position"""
        comps = []
        for i, m in enumerate(move):
            if i != 0 and m != move[-1] and (board[m] != -1 or m in hit_set):
                continue
            hit = m > 0 and board[m] == -1
            if hit:
                if m in hit_set:
                    hit = False
                    assert m == move[-1]
                else:
                    hit_set.add(m)
            comps += ['%s%s' % (self._point_name(m), '*' if hit else '')]
        return '/'.join(comps) + ('' if mult == 1 else '(%d)' % mult)
        
    def _make_move(self, board, moves):
        moves = list(moves)
        # Join up single checker moves
        while self._join_combo(moves):
            pass
        # Combine duplicate moves together
        moves = map(lambda x:(x[0], len(list(x[1]))), itertools.groupby(moves))
        hits = set()
        return ' '.join(self._nice_move(mv, c, hits, board) for mv, c in moves)

class GameState(object):
    "The state of a game being played."
    def __init__(self, crawford=False):
        self.board = initialPosition
        self.dice = None
        self.cube = (None, 1)
        self.offer = None
        self.crawford = crawford
    _keys = ['board', 'dice', 'cube', 'offer', 'crawford']
    @property
    def kwargs(self):
        return dict((k, getattr(self, k)) for k in self._keys)


class GameMove(object):
    "Base class for the things a player can do in a game."
    @property
    def report(self):
        return 'Player %d %s.' % (self.player, self)
    @property
    def _report(self):
        return str(self)
    def __str__(self):
        return 'Erroneous move type %s' % type(self)
    _jelly_export = ''
    def apply(self, game_state):
        game_state.dice = None
        game_state.offer = None
    @property
    def action(self):
        "A short version of the type (eg 'roll')"
        return type(self).__name__.rpartition('GameMove')[2].lower()
        
    
class GameMoveDouble(GameMove):
    "A player doubles."
    def __init__(self, player, to_what):
        self.player = player
        self.double = to_what
    def __str__(self):
        return 'doubles to %d' % self.double
    @property
    def _jelly_export(self):
        return 'Doubles => %d' % self.double
    def apply(self, game_state):
        game_state.dice = None
        game_state.offer = (self.player, self.double)
        
class GameMoveTake(GameMove):
    "A player takes a double."
    def __init__(self, player):
        self.player = player
    def __str__(self): return 'takes'
    _jelly_export = 'Takes'
    def apply(self, game_state):
        game_state.dice = None
        game_state.offer = None
        game_state.cube = (self.player, game_state.cube[1] * 2)
        
class GameMoveDrop(GameMove):
    "A player drops a cube."
    def __init__(self, player):
        self.player = player
    def __str__(self): return 'drops'
    _jelly_export = 'Drops'
    def apply(self, game_state):
        game_state.dice = None
        game_state.offer = None
    

class GameMoveRoll(GameMove):
    "A player rolls the dice."
    def __init__(self, player, d0, d1):
        self.player = player
        self.dice = d0, d1
    def __str__(self):
        return 'rolls %d%d' % self.dice
    @property
    def _jelly_export(self):
        return '%d%d: ' % self.dice
    def apply(self, game_state):
        game_state.dice = self.dice
        game_state.offer = None

class GameMoveMove(GameMove):
    "A player moves some men."
    def __init__(self, player, move):
        self.player = player
        self.move = move
    def __str__(self):
        if self.move: return 'moves %s' % self.move
        else: return 'cannot move'
    @property
    def _jelly_export(self):
        return self.move.str_simple()
    def apply(self, game_state):
        game_state.dice = None
        game_state.offer = None
        game_state.board = self.move.board_after
        if self.player:
            game_state.board = game_state.board.reverse()

class GameMoveResign(GameMove):
    "A player resigns the game."
    def __init__(self, player, value):
        self.player = player
        self.value = ['single game', 'gammon', 'backgammon'][value - 1]
    def __str__(self):
        return 'resigns a %s' % self.value

class GameMoveWin(GameMove):
    "A player wins the game."
    def __init__(self, player, points):
        self.player = player
        self.points = points
    def __str__(self):
        return 'wins %d point%s' % (self.points, 's' * (self.points != 1))
    @property
    def _jelly_export(self):
        return str(self).capitalize()

class GameMoveWinmatch(GameMoveWin):
    "A player wins the game, which ends the match."
    def __str__(self):
        return GameMoveWin.__str__(self) + ' and the match'
    
def _merger(seq, merge_status, f, combine):
    """Given a sequence 'seq', yield f applied to each of the elements.
    Except if 'b' follows 'a' with merge_status(a)[0] and merge_status(b)[1]
    then we combine the two, by yielding combine(f(a, b)) instead."""
    merged = None
    for a in seq:
        can_start, can_continue = merge_status(a)
        if merged and can_continue:
            yield combine(merged, f(a))
            merged = None
        else:
            if merged:
                yield merged
                merged = None
            if can_start:
                merged = f(a)
            else:
                yield f(a)
    if merged: yield merged
        
class Game(object):
    "A single game of backgammon."
    def __init__(self, moves, score=(0, 0), players=None, match_length=0,
            game_number=0, crawford=False):
        self.score = score
        self._moves = list(moves)
        self.players = players or ('Player0', 'Player1')
        self.match_length = match_length
        self.game_number = game_number
        self.crawford = crawford
    
    def replay(self):
        "Generate pre-state, move and post-state for each move in the game."
        game_state = GameState(crawford=self.crawford)
        for move in self:
            pre_state = copy.copy(game_state)
            move.apply(game_state)
            yield pre_state, move, game_state
    
    def report(self):
        "Return a log of all moves in the game"
        def comma_and(g):
            "Join strings together with ', ' but use 'and' for the last one."
            g = list(g)
            if len(g) == 1: return g[0]
            return ', '.join(g[:-1]) + ' and ' + g[-1]
            
        for p, moves in itertools.groupby(self, lambda x:x.player):
            yield 'Player %d %s.' % (p, comma_and(map(str, moves)))
        
    def export_jellyfish_mat_breakmoves(self, moves):
        "Merge together rolls and their subsequent moves"
        def merge_status(m):
            return isinstance(m, GameMoveRoll), isinstance(m, (GameMoveMove, GameMoveWin))
        return _merger((m for m in moves if m._jelly_export),
            merge_status, lambda a:a._jelly_export, operator.add)
    def _jelly_lines(self):
        """Generate basic lines of jellyfish match. Rolls and moves are
        grouped together, and player 1's moves are on the same line as
        player 0's moves when that makes sense. This doesn't include move
        numbers, and the two columns are returned as a tuple rather than
        a packed string."""
        def merge_status(x): return not x[0], x[0]
        def combine(a, b): return True, a[1], b[2]
        def f(a):
            player, move = a
            return not move.strip().startswith('Win'), \
                (move if not player else ''), (move if player else '')
        def move_seq():
            "Moves of the game, with rolls merged with moves, grouped by player"
            # Ignore moves with no jellyfish export
            game_record = (m for m in self if m._jelly_export)
            grouped_by_player = itertools.groupby(game_record, lambda x:x.player)
            for p, moves in grouped_by_player:
                for a in self.export_jellyfish_mat_breakmoves(moves):
                    yield p, a
        return _merger(move_seq(), merge_status, f, combine)
    def export_jellyfish_mat(self):
        "Generate lines of a jellyfish match compatible record of the game."
        # Game header
        yield ' Game %d' % self.game_number
        # Score header for game
        scores = ['%s : %d' % (self.players[i], self.score[i] + self.match_length)
            for i in xrange(2)]
        yield ' %-30s %s' % (scores[0], scores[1])
        # And numbered moves of the game, in 2 columns.
        for i, x in enumerate(self._jelly_lines()):
            if x[0]: yield (' %2d) %-27s %s' % (i + 1, x[1], x[2]))
            else: yield (' %-32s %s' % (x[1], x[2])).rstrip()
            
    @property
    def result(self):
        for m in self._moves:
            if isinstance(m, GameMoveWin):
                return m.player, m.points
        return None
        
    def __iter__(self):
        for m in self._moves:
            yield m

class Match(object):
    "A backgammon match"
    def __init__(self):
        self._playername = ['', '']
        self._games = []
    def export_jellyfish_mat(self):
        "Generate the lines of a jellyfish match file."
        yield '%d point match' % self.length
        for g in self:
            yield ''
            for line in g.export_jellyfish_mat():
                yield line
    def report(self):
        "Generate lines describing the match"
        yield 'Match to %d' % self.length
        for g in self:
            yield ''
            for line in g.report():
                yield line
                
    def player(self, i):
        "The name of one of the players"
        return self._playername[i]
    @property
    def length(self):
        "Match length (0 = money game)"
        return self._length
    @property
    def games(self):
        return list(self._games)
    def __iter__(self):
        for g in self._games:
            yield g
